{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面扩充到 **C++23** 的主要标准容器（含新加入的 `flat_*` 容器）之简化实现要点表。依旧强调：这些仅为教学用的“骨架”思路，真实标准实现需处理异常安全、迭代器有效性、内存对齐、分配器等复杂细节。\n",
    "\n",
    "| 容器                                                  | 首次出现在标准 | 底层结构（简化）                    | 关键操作思路                                  | 迭代器/复杂度                        | 备注                      |\n",
    "| ----------------------------------------------------- | -------------- | ----------------------------------- | --------------------------------------------- | ------------------------------------ | ------------------------- |\n",
    "| `std::array<T, N>`                                    | C++11          | 固定原生数组 `T data[N];`           | 编译期确定容量；构造/析构一次完成             | 随机迭代器；全部 O(1)                | 不可扩缩容                |\n",
    "| `std::vector<T>`                                      | C++98          | 动态数组 `T* data; size; capacity;` | `push_back` 时按策略扩容（常用 ×2）；搬迁元素 | 扩容使指针/迭代器失效；随机访问 O(1) | 需处理构造/析构与异常安全 |\n",
    "| `std::deque<T>`                                       | C++98          | 分段数组（块表 + 块内固定数组）     | 前后插入通过增减块；随机访问先定位块          | 块重排时迭代器失效；访问 O(1)        | 实现难点是块调度          |\n",
    "| `std::list<T>`                                        | C++98          | 双向链表 `prev/next/value`          | 插入/删除只改指针                             | 迭代器稳定；无随机访问               | 常用哨兵节点简化边界      |\n",
    "| `std::forward_list<T>`                                | C++11          | 单链表 `next/value`                 | 仅前向迭代；依赖“前驱”迭代器插删              | 迭代器单向；操作 O(1)                | 头结点充当哨兵            |\n",
    "| `std::set<T>` / `std::map<K,V>`                       | C++98          | 平衡 BST（红黑树/AVL）              | 插删时保持平衡（旋转+颜色）                   | 非被删节点迭代器稳定；O(log n)       | 节点含父/子/颜色          |\n",
    "| `std::multiset` / `std::multimap`                     | C++98          | 同上，允许重复键                    | 在等价键范围插入                              | 同上                                 | 需维持等价键顺序          |\n",
    "| `std::unordered_set` / `std::unordered_map`           | C++11          | 哈希表（桶 + 链表/开放寻址）        | 按负载因子 `rehash`；桶内链表存元素           | `rehash` 使迭代器失效；均摊 O(1)     | 简化实现常用“拉链法”      |\n",
    "| `std::unordered_multiset` / `std::unordered_multimap` | C++11          | 同上，允许重复                      | 桶内追加或维护等价链                          | 同上                                 | 需要稳定桶内顺序          |\n",
    "| `std::stack` / `std::queue`                           | C++98          | 适配器（默认 `deque`）              | 仅转发 push/pop/front/back                    | 依赖底层容器                         | 核心是封装接口            |\n",
    "| `std::priority_queue`                                 | C++98          | 适配器（`vector` + 二叉堆）         | `push` 上滤，`pop` 下滤                       | push/pop O(log n)                    | 可自定义比较器            |\n",
    "| `std::basic_string` (`std::string`)                   | C++98          | 类 `vector<char>` + SSO             | 小字符串栈存，大字符串堆存；确保 `'\\0'`       | 类似 `vector` 语义                   | 简化实现可先忽略 SSO      |\n",
    "\n",
    "### C++20~23 引入/强化的容器与适配器\n",
    "\n",
    "| 容器                                             | 首次  | 底层结构（简化）                              | 关键思路                                           | 迭代器/复杂度            | 备注                                 |\n",
    "| ------------------------------------------------ | ----- | --------------------------------------------- | -------------------------------------------------- | ------------------------ | ------------------------------------ |\n",
    "| `std::span<T>`*                                  | C++20 | 指针 + 长度视图                               | 不拥有数据，仅包装 `[ptr, ptr+len)`                | 迭代器即指针；操作 O(1)  | 虽非容器，但常与容器实现关联         |\n",
    "| `std::pmr::vector` 等 PMR 容器                   | C++17 | 与对应容器相同                                | 通过 `polymorphic_allocator` 抽象内存资源          | 同对应容器               | 关键在可切换内存资源                 |\n",
    "| `std::flat_set<T>` / `std::flat_multiset<T>`     | C++23 | 排序 `std::vector<T>`                         | 插入保持有序（通常二分 + 插入）；查找二分          | 查找 O(log n)；插入 O(n) | 迭代器即向量迭代器；缓存友好         |\n",
    "| `std::flat_map<K,V>` / `std::flat_multimap<K,V>` | C++23 | 排序 `std::vector<std::pair<K,V>>` 或平行向量 | 查找/等价操作同上                                  | 同上                     | 适用于批量构建、读多写少场景         |\n",
    "| `std::mdspan`*                                   | C++23 | 指针 + 形状/布局/访问策略                     | 多维视图；不拥有存储                               | 迭代语义依赖策略         | 虽非容器，但常与“自定义数组”实现相关 |\n",
    "| `std::basic_string` C++23 强化                   | C++23 | 同前                                          | 增加 `resize_and_overwrite` 等接口，便于自定义写入 | —                        | 底层策略同 `vector`，仅接口增强      |\n",
    "\n",
    "\\* `std::span`、`std::mdspan` technically 属于“视图”(view)，但在实现容器或容器适配器时非常常用，因此一并列出。\n",
    "\n",
    "### 简化实现的共通步骤（适用于 C++23 新容器）\n",
    "\n",
    "1. **存储策略**：决定使用“节点式”（树/链表）还是“平面式”（`vector`/数组）。C++23 `flat_*` 利用平面式减少指针开销。\n",
    "2. **平衡/排序维护**：树形容器需实现旋转；平面排序容器需保持有序（可延迟排序或批量建树）。\n",
    "3. **迭代器语义**：保证 `begin()/end()`、反向迭代器、常量迭代器在修改后满足标准要求。\n",
    "4. **异常与强保证**：插入、扩容等需至少达到基本异常安全；`flat_*` 插入可通过临时缓冲实现强保证。\n",
    "5. **与分配器/内存资源集成**：C++17 起可接入 `std::pmr::*`，实现时需分离“逻辑容器”与“内存提供者”。\n",
    "\n",
    "如需具体容器（例如 `flat_map` 或 `mdspan`）的简化代码样例，请继续告知。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "name": "C++17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
